/**
 *  Queue - Array Implementation
 *
 */

class QueueArray<T> {
    
    private T[] arr;
    private int total, first, last;

    public QueueArray() {
        arr = (T[]) new Object[1];
    }

    public void enqueue(T t) {
        if (total == arr.length) {
            resize(arr.length * 2);
        }

        arr[last++] = t;
        if (last == arr.length) {
            last = 0;
        }

        total++;
    }

    public T dequeue() {
        if (total == 0) {
            return null;
        }

        T t = arr[first];
        arr[first] = null;
        total--;

        if (++first == arr.length) {
            first = 0;
        }

        if (total == arr.length / 4) {
            resize(arr.length / 2);
        }

        return t;
    }

    public T peek() {
        if (total == 0) {
            return null;
        }

        return arr[first];
    }

    private void resize(int capacity) {
        T[] tmp = (T[]) new Object[capacity];

        for (int i = 0; i < total; i++) {
            tmp[i] = arr[(first + i) % arr.length];
        }

        arr = tmp;

        first = 0;
        last = total;
    }

    public int size() {
        return total;
    }

    public Boolean isEmpty() {
        return total == 0;
    }

}
